package zuo.algo.c10;

/**
 * 01:53
 * 给定两个长度都为N的数组weights和values，weights[i]和values[i]分别代表
 * i号物品的重量和价值。给定一个正数bag，表示一个载重bag的袋子，你装的物
 * 品不能超过这个重量。返回你能装下最多的价值是多少?
 */
public class Knapsack {

    public static int exc1(int[] weight, int[] values, int bag) {
        return process(weight, values, bag, 0, 0);
    }

    public static int process(int[] weight, int[] values, int bag, int prevWeight, int i) {
        if (prevWeight >= bag) {
            return 0;
        }
        if (i == weight.length) {
            return 0;
        }
        int curWeight = weight[i];
        if ((prevWeight + curWeight) > bag) {
            return process(weight, values, bag, prevWeight, i + 1);
        }
        return Math.max(process(weight, values, bag, prevWeight, i + 1),
                values[i] + process(weight, values, bag, prevWeight + curWeight, i + 1));
    }

    public static void main(String[] args) {
        int[] weight = new int[] {1, 2, 3, 4};
        int[] values = new int[] {4, 8, 2, 5};
        System.out.println(exc1(weight, values, 3));
    }
}
